#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <math.h>
#include "Queue.h"
typedef int BinaryTreeDataType;
typedef struct BinaryTreeNode
{
	BinaryTreeDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(int x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

//二叉树的创建
BTNode* CreatBinaryTree(int* arr,int* pi)
{
	if (arr[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* new = (BTNode*)malloc(sizeof(BTNode));
	new->data = arr[(*pi)++];
	new->left = CreatBinaryTree(arr, pi);
	new->right = CreatBinaryTree(arr, pi);

	return new;
}

//二叉树的销毁
void binarytreedestory(BTNode* root)
{
	//后序销毁，先销毁左子树，再销毁右子树，最后销毁根
	if (root == NULL)
	{
		return;
	}
	binarytreedestory(root->left);
	binarytreedestory(root->right);
	free(root);
}


//二叉树的前序遍历
//根 左子树 右子树
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL");
		return;
	}

	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

//二叉树的中序遍历
//左子树 根 右子树
void MIddleOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL");
		return;
	}

	MIddleOrder(root->left);
	printf("%d ", root->data);
	MIddleOrder(root->right);
}

//二叉树的后序遍历
//左子树 右子树 根
void AfterOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL");
		return;
	}

	AfterOrder(root->left);
	AfterOrder(root->right);
	printf("%d ", root->data);
}

static int size = 0;

// 二叉树节点个数
int GetBinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	return GetBinaryTreeSize(root->left) + GetBinaryTreeSize(root->right) + 1;
}

//叶子节点的个数
int GeBinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	else
	{
		return GeBinaryTreeLeafSize(root->left) + GeBinaryTreeLeafSize(root->right);
	}
}

//二叉树的深度
int GetBinaryTreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	return (int)fmax(GetBinaryTreeHeight(root->left), GetBinaryTreeHeight(root->right)) + 1;
}


////二叉树的深度
//int GetBinaryTreeHeight(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//
//	int leftheight = GetBinaryTreeHeight(root->left);
//	int rightheight = GetBinaryTreeHeight(root->right);
//
//	return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
//}


//有效率问题
//二叉树的高度
//int GetBinaryTreeHeight(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	else
//	{
//		return GetBinaryTreeHeight(root->left) > GetBinaryTreeHeight(root->right) ?
//			GetBinaryTreeHeight(root->left) + 1 :
//			GetBinaryTreeHeight(root->right) + 1;
//	}
//}

// 二叉树第k层节点个数
int GetBinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	else if (1 == k)
	{
		return 1;
	}
	k--;
	return GetBinaryTreeLevelKSize(root->left, k) + GetBinaryTreeLevelKSize(root->right, k);
}

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BinaryTreeDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* ret1 = BinaryTreeFind(root->left,x);
	if (ret1->data == x)
	{
		return ret1;
	}
	BTNode* ret2 = BinaryTreeFind(root->right,x);
	if (ret2->data == x)
	{
		return ret2;
	}
	return NULL;
}

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue a = { 0 };
	QueueInit(&a);

	//先将根插入到队列中
	QueuePush(&a, root);

	//队列不为空就执行删除元素，并插入其儿子
	while (!QueueEmpty(&a))
	{
		//获取队头元素
		BTNode* front = GetQueueFront(&a);
		
		//将该元素删除
		QueuePop(&a);

		//打印该元素
		printf("%d ", front->data);

		//将该元素的儿子插入到队列中
		if (front->left)
		{
			QueuePush(&a, front->left);
		}
		if (front->right)
		{
			QueuePush(&a, front->right);
		}
	}

	QueueDestroy(&a);
}

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue a = { 0 };
	QueueInit(&a);

	//先将根插入到队列中
	QueuePush(&a, root);

	//队列不为空就执行删除元素，并插入其儿子
	while (!QueueEmpty(&a))
	{
		//获取队头元素
		BTNode* front = GetQueueFront(&a);

		//将该元素删除
		QueuePop(&a);

		//检查取出来的数据为不为空
		if (front == NULL)
		{
			//判断队列里面的元素是否全为NULL
			//如果全为NULL，则是完全二叉树
			//如果不全为NULL，则不是完全二叉树
			while (!GetQueueFront(&a))
			{
				QueuePop(&a);
				if (QueueEmpty(&a))
				{
					QueueDestroy(&a);
					return true;
				}
			}
			break;
		}

		//将该元素的儿子插入到队列中
		QueuePush(&a, front->left);
		QueuePush(&a, front->right);
	}

	QueueDestroy(&a);
	return false;
}

//int main()
//{
//	//int arr[] = { 1,2,3,4,5,6};
//	//BTNode* root = NULL;
//	//int i = 0;
//	//root = CreatBinaryTree(arr,&i);
//
//	//BinaryTreeLevelOrder(root);
//
//	//PrevOrder(root);
//	//printf("\n");
//	//MIddleOrder(root);
//	//printf("\n");
//	//AfterOrder(root);
//	//printf("\n");
//
//	//printf("TreeHeight:%d\n", GetBinaryTreeHeight(root));
//
//	//printf("TreeLeafSize:%d\n", GeBinaryTreeLeafSize(root));
//
//	//printf("TreeNodeSize:%d\n", GetBinaryTreeSize(root));
//
//	//printf("The %d NodeSize:%d\n", 1,GetBinaryTreeLevelKSize(root,1));
//	//printf("The %d NodeSize:%d\n", 2,GetBinaryTreeLevelKSize(root,2));
//	//printf("The %d NodeSize:%d\n", 3,GetBinaryTreeLevelKSize(root,3));
//
//	//BTNode* ret = BinaryTreeFind(root, 2);
//	//printf("%d\n", ret->data);
//
//	return 0;
//}

int main()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	BTNode* node7 = BuyNode(7);

	node1->left = node2;
	node2->left = node3;
	node1->right = node4;
	node4->left = node5;
	node4->right = node6;
	node2->right = node7;
	BTNode* root = node1;

	BinaryTreeLevelOrder(root);
	printf("\n");

	if (BinaryTreeComplete(root))
	{
		printf("complete\n");
	}
	else
	{
		printf("noComplete\n");
	}
	return 0;
}